#include <iostream>
#include <fstream>
#include "tree.h"

template <class T>
void BinaryTree<T>::CreateBinaryTree(ifstream& in, BinaryTreeVertex<T>*& subtree) {
	T item;
	if (!in.eof()) {
		in >> item;
		if (item != EndTag) {
			subtree = new BinaryTreeVertex<T>(item, NULL, NULL);
			if (subtree == NULL) {
				cerr << "Allocation Error!" << endl;
				exit(1);
			}
			CreateBinaryTree(in, subtree->LeftSubtree);
			CreateBinaryTree(in, subtree->RightSubtree);
		}
		else {
			subtree = NULL;
		}
	}
}
template <class T>
void BinaryTree<T>::Destroy(BinaryTreeVertex<T>* subroot) {
	if (subroot != NULL) {
		Destroy(subroot->LeftSubtree);
		Destroy(subroot->RightSubtree);
		delete subroot;
		subroot = NULL;
	}
}
template <class T>
void BinaryTree<T>::PreOrder(BinaryTreeVertex<T>* subroot) {
	if (subroot != NULL) {
		cout << subroot->data << " ";
		PreOrder(subroot->LeftSubtree);
		PreOrder(subroot->RightSubtree);
	}
}
template <class T>
void BinaryTree<T>::InOrder(BinaryTreeVertex<T>* subroot) {
	if (subroot != NULL) {
		InOrder(subroot->LeftSubtree);
		cout << subroot->data << " ";
		InOrder(subroot->RightSubtree);
	}
}
template <class T>
void BinaryTree<T>::PostOrder(BinaryTreeVertex<T>* subroot) {
	if (subroot != NULL) {
		PostOrder(subroot->LeftSubtree);
		PostOrder(subroot->RightSubtree);
		cout << subroot->data << " ";
	}
}
template <class T>
int BinaryTree<T>::Height(BinaryTreeVertex<T>* subroot) {
	if (subroot == NULL) {
		return 0;
	}
	int NumberLeft = Height(subroot->LeftSubtree);
	int NumberRight = Height(subroot->RightSubtree);
	return NumberLeft > NumberRight ? (NumberLeft + 1) : (NumberRight + 1);
}
template <class T>
int BinaryTree<T>::Size(BinaryTreeVertex<T>* subroot) {
	if (subroot == NULL) {
		return 0;
	}
	int NumberLeft = Size(subroot->LeftSubtree);
	int NumberRight = Size(subroot->RightSubtree);
	return NumberLeft + NumberRight + 1;
}
template <class T>
BinaryTree<T>::BinaryTree() {
	root = NULL;
}
template <class T>
BinaryTree<T>::BinaryTree(T value) {
	EndTag = value;
	root = NULL;
}
template <class T>
BinaryTree<T>::~BinaryTree() {
	Destroy(root);
}
template <class T>
bool BinaryTree<T>::IsEmpty() {
	return root == NULL;
}
template <class T>
int BinaryTree<T>::Height() {
	return Height(root);
}
template <class T>
int BinaryTree<T>::Size() {
	return Size(root);
}
template <class T>
void BinaryTree<T>::CreatePreOrder(ifstream& in) {
	CreateBinaryTree(in, root);
}
template <class T>
void BinaryTree<T>::PreOrder() {
	PreOrder(root);
}
template <class T>
void BinaryTree<T>::InOrder() {
	InOrder(root);
}
template <class T>
void BinaryTree<T>::PostOrder() {
	PostOrder(root);
}
template <class T>
BinaryTreeVertex<T>* BinaryTree<T>::GetRoot() {
	return root;
}